c=59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
e=65537
n=113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
p1=7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
kbits=512 - p1.nbits()
p1 = p1 << kbits


def phase3(high_p, n):
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    p = high_p + x
    x0 = p.small_roots(X=2 ^ kbits, beta=0.2)[0]
    P = int(p(x0))
    Q = n // P
    assert n == P * Q
    return P, Q


p, q = phase3(p1, n)
print(p)
print(q)
phi = (p - 1) * (q - 1)
d = libnum.invmod(e, phi)
m = pow(c, d, n)
print(libnum.n2s(int(m)))